Coin Change
Question
There is a coin machine that gives you infinite amount of coins of certain values. Given this list of values and a total target value, return the fewest coins needed to sum up to the target.
If there are no combinations of coints that can sum up to the target, return -1.
Input: coins = [1, 2, 5], target = 11
Output: 3
11 = 5 + 5 + 1
The fewest number of coins needed to sum up to 11 is 3 coins. We can reach the target with these combinations:
- 11 coins: 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
- 3 coins: 5 + 5 + 1
Input: coins = [2, 5, 10], target = 20
Output: 2
The fewest number of coins needed to sum up to 20 is 2 coins. We can reach the target with these combinations:
- 10 coins: 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2
- 6 coins: 10 + 2 + 2 + 2 + 2 + 2
- 4 coins: 5 + 5 + 5 + 5
- 3 coins: 10 + 5 + 5
- 2 coins: 10 + 10
Input: coins = [2], target = 3
Output: -1
There are no combinations of coins that will sum up to 3 in this case.
Clarify the problem
What are some questions you'd ask an interviewer?
Understand the problem
Take a moment to understand the problem and think of your approach before you start coding.
